//给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
//
//
//
// 示例 1:
//
//
//输入: nums = [1,1,1,2,2,3], k = 2
//输出: [1,2]
//
//
// 示例 2:
//
//
//输入: nums = [1], k = 1
//输出: [1]
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10⁵
// k 的取值范围是 [1, 数组中不相同的元素的个数]
// 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
//
//
//
//
// 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
// Related Topics 数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列） 👍 995 👎 0

package leetcode.editor.cn;

import java.util.*;

@SuppressWarnings("all")
//Java：前 K 个高频元素
public class TopKFrequentElements {
    public static void main(String[] args) {
        Solution solution = new TopKFrequentElements().new Solution();
        // TO TEST
        int[] nums = {1, 1, 1, 2, 2, 3};
        solution.topKFrequent(nums, 2);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            if (k == nums.length)
                return nums;
            return qSort(nums, k);
        }

        public Map<Integer, Integer> counts(int[] nums) {
            Map<Integer, Integer> counts = new HashMap<>();
            // 统计出现的次数
            for (int num : nums) {
                counts.put(num, 1 + counts.getOrDefault(num, 0));
            }
            return counts;
        }

        // 利用维护k个元素的小顶堆,寻找topK
        private int[] heap(int[] nums, int k) {

            PriorityQueue<int[]> queue = new PriorityQueue<>((Comparator.comparingInt(o -> o[1])));

            Map<Integer, Integer> counts = counts(nums);

            counts.forEach((num, count) -> {
                if (queue.size() == k) {
                    assert queue.peek() != null;
                    if (queue.peek()[1] < count) {
                        queue.remove();
                        queue.offer(new int[]{num, count});
                    }
                } else queue.offer(new int[]{num, count});

            });

            int[] res = new int[k];

            int index = 0;
            while (!queue.isEmpty()) {
                int[] count = queue.poll();
                int num = count[0];
                res[index++] = num;
            }

            return res;
        }

        public int[] qSort(int[] nums, int k) {
            Map<Integer, Integer> counts = counts(nums);
            List<int[]> ans = new ArrayList<>();

            counts.forEach((num, count) -> ans.add(new int[]{num, count}));

            qSort(ans, 0, ans.size() - 1);

            int[] res = new int[k];
            int index = 0;
            for (int i = ans.size() - 1; i >= ans.size() - k; i--) {
                res[index++] = ans.get(i)[0];
            }
            return res;

        }

        public void qSort(List<int[]> nums, int start, int end) {

            int target = nums.get(start)[1], left = start, right = end;

            while (left < right) {
                while (left < right) {
                    if (nums.get(right)[1] < target) {
                        Collections.swap(nums, left, right);
                        break;
                    } else right--;
                }

                while (left < right) {
                    if (nums.get(left)[1] > target) {
                        Collections.swap(nums, left, right);
                        break;
                    } else left++;
                }


            }

            if (left - 1 > start) {
                qSort(nums, start, left - 1);
            }

            if (right + 1 < end) {
                qSort(nums, right + 1, end);
            }
        }


    }


//leetcode submit region end(Prohibit modification and deletion)


}
